//
// Description: 433. 最小基因变化
// Created by Loading on 2025/7/27.
//

#include <bits/stdc++.h>

using namespace std;

int minMutation(string startGene, string endGene, vector<string> &bank) {
    if (startGene == endGene) {
        return 0;
    }

    unordered_set<string> bank_set;
    for (auto &s : bank) {
        bank_set.emplace(s);
    }
    if (!bank_set.count(endGene)) { // end不在基因库中
        return -1;
    }

    vector<char> all{'A', 'C', 'G', 'T'}; // 所有元素
    unordered_set<string> visit; // 是否访问过
    queue<string> q;
    q.emplace(startGene);
    visit.emplace(startGene);
    int res = 1;
    while (!q.empty()) {
        int n = q.size();
        // 遍历队列中的每个基因序列
        for (int i = 0; i < n; ++i) {
            auto current = q.front();
            q.pop();
            for (int j = 0; j < 8; ++j) {
                for (int k = 0; k < 4; ++k) {
                    auto next = current;
                    if (next[j] != all[k]) {
                        next[j] = all[k]; // 枚举修改每个元素
                        if (!visit.count(next) && bank_set.count(next)) { // 下一个序列 未被访问过 且 在基因库中
                            if (next == endGene) {
                                return res;
                            }
                            visit.emplace(next);
                            q.emplace(next);
                        }
                    }
                }
            }
        }
        ++res;
    }

    return -1;
}

int main() {
    auto startGene = "AACCGGTT";
    auto endGene = "AAACGGTA";
    vector<string> bank{"AACCGGTA", "AACCGCTA", "AAACGGTA"};

    auto res = minMutation(startGene, endGene, bank);

    cout << res << endl;

    return 0;
}